"""
    python实现二叉树
"""


class TreeNode:
    """节点类:创建节点"""
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


class BinaryTree:
    def __init__(self):
        """
        初始化一棵空树: 树根为None为空树
        """
        self.root = None

    def add(self, item):
        """
        二叉树中添加一个节点
        :param item: 数据区
        :return: None
        """
        node = TreeNode(item)
        if not self.root:
            self.root = node
            return

        # 队列思想: append() + pop(0)
        node_queue = [self.root]
        while True:
            cur_node = node_queue.pop(0)
            # 1.判断左孩子
            if cur_node.left:
                node_queue.append(cur_node.left)
            else:
                cur_node.left = node
                break

            # 2.判断右孩子
            if cur_node.right:
                node_queue.append(cur_node.right)
            else:
                cur_node.right = node
                break

    def breadth_travel(self):
        """
        广度遍历: 从上到下,从左到右
        """
        # 1.空树情况
        if not self.root:
            return None

        # 2.非空树情况
        node_queue = [self.root]
        while node_queue:
            cur_node = node_queue.pop(0)
            print(cur_node.val, end=" ")
            # 1.添加左孩子
            if cur_node.left:
                node_queue.append(cur_node.left)

            # 2.添加右孩子
            if cur_node.right:
                node_queue.append(cur_node.right)

        print()

    def front_travel(self, root):
        print()



if __name__ == '__main__':
    bt = BinaryTree()
    bt.add(1)
    bt.add(2)
    bt.add(3)
    bt.add(4)
    bt.add(5)
    bt.add(6)
    bt.add(7)
    bt.add(8)
    bt.add(9)
    # 测试方法
    # 终端1: 1 2 3 4 5 6 7 8 9
    bt.breadth_travel()















